//
//  main.c
//  堆的实现
//
//  Created by 仲7 on 2025/5/17.
//
#include"heap.h"
void HpInit(HP* php)
{
    assert(php);
    php->arr = NULL;
    php->capacity = php->size = 0;
}
void HpDestroy(HP* php)
{
    assert(php);
    if(php->arr)
    {
        free(php->arr);
    }
    php->arr = NULL;
    php->size = php->capacity = 0;
}
void Swap(int* x,int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
//向上调整算法
//O(logN)
void Adjustup(HPDataType* arr,int child)
{
    int parent = (child-1)/2;
    while(child > 0 && arr[child] < arr[parent])
    {
        Swap(&arr[child],&arr[parent]);
        //交换了之后，要更新child 和 parent 的大小
        child = parent;
        parent = (child-1)/2;
    }
    
}
//插入
void HPPush(HP* php,HPDataType x)
{
    assert(php);
    //判断空间是否足够
    if(php->size == php->capacity)
    {
        int Newcapacity = php->capacity == 0? 4: php->capacity * 2;
        HPDataType* tmp = (HPDataType* )realloc(php->arr, Newcapacity * sizeof(HPDataType));
        if(tmp == NULL)
        {
            perror("realloc fail");
            exit(1);
        }
        php->arr = tmp;
        php->capacity = Newcapacity;
    }
    php->arr[php->size++] = x;
    //向上调整算法：将小值向上移动
    Adjustup(php->arr, php->size-1);//此时要传入的是 child 的下标，所以是 size-1
}
//向下调整算法
void Adjustdown(HPDataType* arr,int parent,int n)//形参包括（数组，根节点，总节点数（防止越界））
{
    //由父节点找到左孩子
    int child = parent* 2 + 1;
    while(child < n)
    {
        if(child+1<n && arr[child] > arr[child+1])
        {
            ++child;
        }
        if(arr[child] < arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = child*2 + 1;
        }
        else
        {
            break;
        }
    }
}
//出堆
void HPPop(HP* php)
{
    assert(php);
    assert(php->size);
    //首先交换头尾数据,然后删掉尾部数据
    Swap(&php->arr[0], &php->arr[php->size-1]);
    --php->size;
    //把头部数据向下调整
    Adjustdown(php->arr,0,php->size);
    //比较左右孩子谁小（这里是小堆），谁小谁与头部数据交换。
    //判断比较父节点与子节点大小，进行交换后并更新父子节点位置
}
//取堆顶元素
HPDataType HPTop(HP* php)
{
    assert(php && php->size);
    return php->arr[0];
}
//判空函数
bool HPEmpty(HP* php)
{
    assert(php);
    return php->size == 0;
}
